Tỉnh được thành lập vào ngày 2 tháng 4 [22 tháng 3 lịch cũ] năm 1764 với tư cách là một quân khu để bảo vệ biên giới phía nam của đế quốc và để chuẩn bị cho chiến dịch quân sự lớn trong Chiến tranh Nga-Thổ Nhĩ Kỳ. Tỉnh thống nhất các lãnh thổ của Tân Serbia, Slavo-Serbia và Trung đoàn Slobidskyi (ngày nay ở tỉnh Kirovohrad) là các khu vực phía bắc của Buhohard Palatinate (Sich Zaporizhia). Tỉnh tập trung ở pháo đài Thánh Elizaveta, ban đầu được chia thành ba lãnh thổ (polki) được gắn với mỗi trung đoàn trong khu vực: Trung đoàn giáo mác Thành phố Elizabeth, Trung đoàn kỵ binh Hussar Đen và Trung đoàn kỵ binh Hussar Vàng.

Kể từ ngày 22 tháng 6 [11 tháng 6 lịch cũ] 1764, tỉnh này cũng bao gồm cái gọi là Phòng tuyến Ukraina, một tuyến gồm các pháo đài do Nga xây dựng nằm giữa sông Dnepr và sông Donets, được quản lý bởi các trung đoàn giáo mác Dnepr và Donets (dựa theo Pandur của Habsburg, người Cossack của Poltava, các trung đoàn Myrhorod), Slavo-Serbia với Trung đoàn giáo mác Lugansk, và các trung đoàn kỵ binh Hussar Raiko Preradovic và Ivan Sevic (ngay sau đó hai trung đoàn này được hợp nhất thành Trung đoàn kỵ binh Hussar Bakhmut) cũng như Trung đoàn kỵ binh Hussar Samara (ban đầu là Trung đoàn kỵ binh Moldavia có trụ sở tại Kiev).

Thủ phủ đầu tiên của tỉnh là thành phố Kremenchug (1765) với pháo đài Thánh Elizaveta (ngày nay là Kropyvnytskyi) phục vụ chức năng hành chính trước đó (1764).

Vào năm 1769–70 trong Chiến tranh Nga-Thổ Nhĩ Kỳ, đã có một cuộc nổi dậy trong các trung đoàn quân giáo mác Dnepr và Donets.[2] Tình trạng bất ổn bắt đầu trên lãnh thổ của tỉnh Poltava ngày nay và cuối cùng lan rộng khắp các vùng đất của Quân đoàn Zaporizhia.[2] Cuộc nổi dậy bị các lực lượng Đế quốc Nga trấn áp không thương tiếc và những kẻ chủ mưu bị trừng phạt bằng knout (roi da) hoặc bị đưa đến katorga (trại lao động).[2] Trung đoàn quân giáo mác Donets cuối cùng bị buộc phải tham chiến với Ottoman, nơi họ đóng vai trò quan trọng trong việc chiếm Syvash, lấy Perekop, Caffa (Feodosiya).[2]

Vào tháng 6 năm 1775, Quân đội Đế quốc Nga đã san bằng thủ đô của Sich Zaporizhia, sau đó tất cả các vùng đất của nó được sáp nhập vào tỉnh Novorossiysk. Năm sau, các vùng Bakhmut và Yekaterina được chuyển giao cho tỉnh Azov mới thành lập.